题解 P4688@洛谷【[Ynoi2016]掉进兔子洞】

题意已经足够清楚了，我们直接说思路：

前置知识：

分块、莫队
离散化
一些奇奇怪怪的技巧

根据题意三段区间的数的总和为 $\sum_{i=1}^3(r_i-l_i+1)-3\times k$ ，其中 $k$ 为三段区间内共有的数的个数。问题转化为求这个 $k$ 的值。

容易想到，我们使用莫队维护查询的区间内每个数的个数。对于一次询问，我们将其拆成传统莫队的三个询问： $(l_1,r_1),(l_2,r_2),(l_3,r_3)$ ，分别进行处理。我们要得到 $k$ ，需要得到这三个询问中有哪些数、分别几个，然后取它们的交集即可。

那么问题来了，这个交集（或三次询问）怎么求呢？注意一个数可能重复出现多次。我们考虑先将初始 $a$ 数组进行离散化，只记录 $a$ 数组每一个值对应排序好的数组的编号即可。这样，若干个相同的数便会留出若干个空着的编号，它们代表同一个值。然后使用这个离散化的对应关系用 bitset 存即可。

完结撒花！

等等，Ynoi 可不是这么简单就过去的。看一眼数据范围， $1\le n,m\le 10^5$ 。bitset 存不下！（笑容逐渐凝固）

没关系，我们可以把输入的查询分为若干组，每组 $2\times 10^4$ 个数（当然更大也可以，不炸空间就没事），对于每一组分别进行处理即可。

小细节：莫队必须先进队再出队！ 我因为一开始顺序搞混一直 RE，被卡了 1.5h！

真·完结撒花！

主要代码：

const ll N = 1e5+5, M = 2e4, K = M+5, SIZE = 320;
ll n, m, a[N], b[N], s[N];
ll vis[N], len[N];
bitset<N> cnts[K], u;
#define whichBlock(x) (\
	(x-1)/SIZE+1\
)
struct Node {
	ll l, r, id;
	friend bool operator < (const Node &a, const Node &b) {
		ll x = whichBlock(a.l), y = whichBlock(b.l);
		if(x == y) return a.r < b.r;
		return x < y;
	}
}q[N];

void discretization() {
	for(ll i=1;i<=n;i++) {
		scanf("%lld", &a[i]);
		b[i] = a[i];
	}
	sort(b+1, b+1+n);
	for(ll i=1;i<=n;i++) a[i] = ll(lower_bound(b+1, b+1+n, a[i]) - b);
}
void modify(ll x, ll y) {
	ll z = a[x];
	if(y == -1) u[z+(--s[z])] = 0;
	else u[z+(s[z]++)] = 1;
}
void solve(ll op) {
	assert(op > 0);
	ll tot = 0;
	memset(s, 0, sizeof(s));
	for(ll i=1;i<=op;i++) {
		vis[i] = len[i] = 0;
		for(ll j=1;j<=3;j++) {
			q[++tot].id = i;
			scanf("%lld%lld", &q[tot].l, &q[tot].r);
			len[i] += q[tot].r - q[tot].l + 1;
		}
	}
	sort(q+1, q+1+tot);
	ll l = 1, r = 0;
	u.reset();
	for(ll i=1;i<=tot;i++) {
		while(l > q[i].l) modify(--l, 1);
		while(r < q[i].r) modify(++r, 1);
		while(l < q[i].l) modify(l++, -1);
		while(r > q[i].r) modify(r--, -1);
		if(vis[q[i].id]) cnts[q[i].id] &= u;
		else cnts[q[i].id] = u;
		vis[q[i].id] = 1;
	}
	for(ll i=1;i<=op;i++) printf("%lld\n", len[i]-3*(ll)cnts[i].count());
}